package cn.dapeng.tree.binary;

/**
 * 判断一个树是否是搜索二叉树
 * <p>
 * <p>
 * 平衡二叉树定义：左树与右树的高度差小于2
 * <p>
 * 搜索二叉树定义： 对于任何子树，左树的任何节点都小于跟节点，右树的任何节点都大于跟节点
 */
public class CheckSearchTree {

    public static boolean isSearchTree(TreeNode head) {
        if (head == null) {
            return true;
        }
        return process(head).isBST;
    }

    public static Info process(TreeNode x) {
        if (x == null) {
            return null;
        }
        // 先把左、右子树的信息收上来
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        // 假设当前节点，左侧最大值和右侧最小值都是当前节点的值
        int minValue = x.val;
        int maxValue = x.val;
        boolean isBST;

        // 搜集左树的最大值和最小值信息
        if (leftInfo != null) {
            maxValue = Math.max(leftInfo.maxValue, maxValue);
            minValue = Math.min(leftInfo.minValue, minValue);
        }
        // 搜集右树的最大值和最小值信息
        if (rightInfo != null) {
            minValue = Math.min(rightInfo.minValue, minValue);
            minValue = Math.min(rightInfo.minValue, minValue);
        }

        // 判断当前节点是否是二叉搜索树
        // 如果左树为空，或者左树是二叉搜索树，并且左树最大值小于当前节点，那么当前节点是二叉搜索树
        // 如果右树为空，或者右树是二叉搜索树，并且右树最小值大于当前节点，那么当前节点是二叉搜索树
        boolean leftIsBST = leftInfo == null || (leftInfo.isBST && leftInfo.maxValue < x.val);
        boolean rightIsBST = rightInfo == null || (rightInfo.isBST && rightInfo.minValue > x.val);

        isBST = leftIsBST && rightIsBST;

        return new Info(isBST, maxValue, minValue);
    }

    public static class Info {
        boolean isBST;

        Integer minValue;
        Integer maxValue;

        public Info(boolean isBST, Integer minValue, Integer maxValue) {
            this.isBST = isBST;
            this.minValue = minValue;
            this.maxValue = maxValue;
        }
    }
}
